Various types of memory devices use large metadata structures to store information about the memory. For example, some memory devices may use a global address table (GAT) to store logical to physical mapping information for the memory device and an inverse global address table (iGAT) to store physical to logical mapping information for the memory device. In certain embodiments, a GAT may use a logical block address (LBA) as a key to a physical block address (PBA) for the memory device. Conversely, an iGAT may use a PBA as a key to an LBA for the memory device. Certain metadata structures such as a GAT or an iGAT may be large and may be stored in block- or page-addressable non-volatile memory rather than in byte-addressable volatile memory. Thus, changing the metadata may involve reading a portion of the metadata structure into volatile memory, modifying that portion, and writing it back to non-volatile memory. To avoid frequent read-modify-write operations, changes to metadata may be aggregated in a queue or buffer, which may be flushed (e.g., periodically, or when full) by writing the changes to the larger metadata structure.